1. Field
The disclosure relates generally to network communication and, more particularly, to resource allocation for network communication.
2. Background
Information communication provided by various forms of networks has nearly become ubiquitous in the world today. Networks comprised of multiple nodes in communication using wireless and wireline links are used, for example, to carry data packets which may convey many types of data payload, such as voice data, multimedia data, alphanumeric data, graphics data, etc. Accordingly, the nodes of such networks may be computers, personal digital assistants (PDAs), phones, servers, routers, switches, multiplexers, modems, radios, access points, base stations, etc. Data packet flows are established between the network nodes to provide desired network communication, wherein the end-to-end data communication for any particular communication session may utilize multiple hops (i.e., be routed through one or more intermediate network node). Any number of the network nodes may be contending for network communication resources for providing such flows at any particular point in time.
A transmission between a pair of network nodes (e.g., wireless network nodes) may cause interference with respect to communications of one or more other network node (e.g., interfere with another transmission between a different pair of network nodes), if these transmissions overlap in time, frequency, and space domains. Hence, the success of such transmissions might only be ensured if they are separated in at least one of the aforementioned domains. A number of techniques for providing resource allocation for shared access to the network communication links may be implemented to facilitate network communications, such as frequency division multiple access (FDMA), time division multiple access (TDMA), spatial separation/isolation, etc. In a TDMA system the frequency domain is not utilized for providing communication orthogonality. For example, in a TDMA system time and space domains may be explored with respect to different transmissions in providing resource allocation for avoiding communication contention (e.g., TDMA operations and spatial reuse options explored for interference avoidance).
It is typically desirable to both meet traffic demand and provide fairness with respect to resource allocation techniques. However, conflicting objectives are present with respect to resource allocation and scheduling in wireless networks. Quality of service (QoS) and fairness are often both important in providing communications yet often times conflict for resource allocation and scheduling in wireless networks. For example, due to the resource sharing nature of various networks, without enforcing fairness, meeting traffic demand or a level of QoS for a subset of network flows may lead to resource starvation of another subset of network flows.
The problem of balancing QoS and fairness becomes more complex when a wireless network spans more than a single hop. This is due to the fact that different resource allocation patterns of two flows that do not contend for resources directly may result in different resource availability situations of a flow that directly contends for resources with the two aforementioned flows. As mentioned above, in TDMA systems time and space domains, for example, may be explored to provide resource allocation which avoids such communication contention. The computational complexity of maximizing the time slot allocation efficiency in TDMA wireless networks by exploiting the spatial reuse is, however, nondeterministic polynomial time (NP-complete), and thus can be quite complex (see A. M. Chou and V. O. K. Li, “Slot Allocation Strategies for TDMA Protocols in Multihop Packet Radio Networks,” Proceedings of IEEE INFOCOM, vol. 2, pp. 710-716, May 1992, the disclosure of which is expressly incorporated herein by reference in its entirety). Several algorithms have been introduced to probabilistically achieve the maximum resource allocation efficiency without any consideration of QoS and fairness (see A. M. Chou and V. O. K. Li, “Slot Allocation Strategies for TDMA Protocols in Multihop Packet Radio Networks,” Proceedings of IEEE INFOCOM, vol. 2, pp. 710-716, May 1992 and P. Bjrklund, P. Vrbrand, and D. Yuan, “Resource Optimization of Spatial TDMA in Ad Hoc Radio Networks: A Column Generation Approach,” Proceedings of IEEE INFOCOM, vol. 2, pp. 818-824, April 2003, the disclosures of which are expressly incorporated herein by reference in their entireties).
QoS and fairness of resource allocation and scheduling in wireless networks have been studied in separate contexts extensively. Accordingly, various fairness measures have been introduced to address the fairness of resource allocation in multi-hop wireless networks. Some such solutions are designed to achieve specific objectives, such as proportional fairness (see e.g., L. B. Jiang and S. C. Liew, “Proportional Fairness in Wireless LANs and Ad Hoc Networks,” Proceedings of IEEE Wireless Communications and Networking Conference (WCNC), vol. 3, pp. 1551-1556, March 2005, the disclosure of which is expressly incorporated herein by reference in its entirety) and max-min fairness (see e.g., X. Huang and B. Bensaou, “On Max-Min Fairness Bandwidth Allocation and Scheduling in Wireless Ad Hoc Networks: Analytical Framework and Implementation,” Proceedings of ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc), pp. 221-231, 2001, the disclosure of which is expressly incorporated herein by reference in its entirety). However, algorithms to achieve these objectives are usually complex and involve an appreciable amount of message exchanges (up to 5 hops away). Other resource allocation algorithms, such as a distributed implementation of a randomized time slot scheduling algorithm (DRAND), provide a level of fairness and spatial reuse in multi-hop ad hoc networks in the absence of specific objective functions (see e.g., I. Rhee, A. Warrier, and J. Min, “DRAND: Distributed Randomized TDMA Scheduling for Wireless Ad Hoc Networks,” Proceedings of ACM MobiHoc, pp. 190-201, 2006, the disclosure of which is expressly incorporated herein by reference in its entirety. Although provided in the absence of specific objective functions, such fairness algorithms involve much less computational complexity and control message exchanges (up to 2 hop away). Nevertheless, all the foregoing fairness based resource allocation algorithms enforce fairness in the absence of QoS requirements.
In contrast to the aforementioned fairness based resource allocation algorithms, various resource allocation and scheduling algorithms have been introduced to solely meet QoS requirements. Some such QoS based resource allocation schemes (see e.g., H. Zhai, “QoS Support Over UWB Mesh Networks,” Proceedings of IEEE Wireless Communications and Networking Conference (WCNC), pp. 2283-2288, March 2008, the disclosure of which is expressly incorporated herein by reference in its entirety) allocate time slot resources on a flow-by-flow basis to meet their traffic demand and can easily lead to unfair data flow congestion situations.
Some resource allocation algorithms have been introduced to address the tradeoff between QoS and fairness by dynamically scheduling time slots based on outstanding traffic loading and data flow contention (see e.g., J. Grnkvist, “Traffic Controlled Spatial Reuse TDMA in Multi-Hop Radio Networks,” Proceedings of IEEE PIMRC, vol. 3, pp. 1203-1207, September 1998 and H. L. Chao and W. Liao, “Credit-Based Slot Allocation for Multimedia Mobile Ad Hoc Networks,” IEEE Journal on Selected Areas in Communications, vol. 21, no. 10, pp. 1642-1651, 2003, the disclosures of which are expressly incorporated herein by reference in their entireties). A gradient method based resource allocation scheme (see e.g., L. Chen, S. H. Low, and J. C. Doyle, “Joint Congestion Control and Media Access Control Design for Ad Hoc Wireless Networks,” Proceedings of IEEE INFOCOM, vol. 3, pp. 2212-2222, March 2005, the disclosure of which is expressly incorporated herein by reference in its entirety) may be utilized to gradually regulate the data rate of each end-to-end data flow so that a utility function can be maximized across the network under the underlying data flow contention constraint. The foregoing schemes, however, require adjusting allocated resources in a highly dynamic manner. Demand assigned TDMA-based wireless networks, such as WiMedia networks (see e.g., “Standard ECMA-368 High Rate Ultra Wideband PHY and MAC Standard,” Url: http://www.ecma-international.org/publications/standards/Ecma-368.htm, December 2008 and “Standard ECMA-387 High Rate 60 gHz PHY, MAC and HDMI PAL,” Url: http://www.ecma-international.org/publications/standards/Ecma-387.htm, December 2008, the disclosures of which are expressly incorporated herein by reference in their entireties), depend on explicit message transactions among wireless devices for resource assignment and expect such resource assignment to be static over a period of time. Accordingly, the aforementioned resource allocation schemes are not suitable to be deployed in demand assigned TDMA wireless networks.